package org.example.myleet.p397;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    private Map<Long, Integer> map;

    public int integerReplacement(int n) {
        map = new HashMap<>();
        return leastOpt(n);
    }

    private int leastOpt(long n) {
        if (n == 1) {
            return 0;
        }
        Integer minOpt = map.get(n);
        if (null == minOpt) {
            minOpt = Integer.MAX_VALUE;
            if ((n & 1) == 1) {
                minOpt = Math.min(minOpt, leastOpt(n + 1) + 1);
                minOpt = Math.min(minOpt, leastOpt(n - 1) + 1);
            } else {
                minOpt = Math.min(minOpt, leastOpt(n >> 1) + 1);
            }
            map.put(n, minOpt);
        }
        return minOpt;
    }
}
